/* 307. 区域和检索 - 数组可修改 */
/* 分块处理 */
/**
 * @param {number[]} nums
 */
var NumArray = function (nums) {
    this.nums = nums
    const n = nums.length
    size = Math.floor(Math.sqrt(n))
    /* 
        最后一个的大小不超过 size 
        记录每个区间的总和
    */
    this.sum = new Array(Math.ceil(n / size)).fill(0)
    for (let i = 0; i < n; i++) {
        this.sum[Math.floor(i / size)] += nums[i]
    }
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.update = function (index, val) {
    /* 更新每个区间的总和 */
    this.sum[Math.floor(index / size)] += val - this.nums[index]
    this.nums[index] = val
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function (left, right) {
    /* b 在哪个快 , i 在当前快中的第几个 */
    const b1 = Math.floor(left / size), i1 = left % size, b2 = Math.floor(right / size), i2 = right % size;
    if (b1 === b2) { // 区间 [left, right] 在同一块中
        let sum = 0;
        for (let j = i1; j <= i2; j++) {
            sum += this.nums[b1 * size + j];
        }
        return sum;
    }
    /* 前半截 */
    let sum1 = 0;
    for (let j = i1; j < size; j++) {
        sum1 += this.nums[b1 * size + j];
    }
    let sum2 = 0;
    /* 后半截 */
    for (let j = 0; j <= i2; j++) {
        sum2 += this.nums[b2 * size + j];
    }
    let sum3 = 0;
    /* 区间和 */
    for (let j = b1 + 1; j < b2; j++) {
        sum3 += this.sum[j];
    }
    return sum1 + sum2 + sum3;


};


/* 
    线段树
    每个节点保存数组nums在区间[s,e]的最小值，最大值或总和等信息 
    可以用数组实现 假设根节点的下标为0,如果一个节点在数组的下标为node 那么它的左子节点下标为
    node * 2 + 1 ，右子节点下标为 node * 2 + 2
*/
var NumArray = function (nums) {
    n = nums.length
    /* n * 4 ? */
    this.segmentTree = new Array(n * 4).fill(0)
    this.build(0, 0, n - 1, nums);
}
NumArray.prototype.update = function (index, val) {
    this.change(index, val, 0, 0, n - 1)
}
NumArray.prototype.sumRange = function (left, right) {
    return this.range(left, right, 0, 0, n - 1)
}
/* 构建 */
NumArray.prototype.build = function (node, s, e, nums) {
    if (s === e) {
        this.segmentTree[node] = nums[s];
        return;
    }
    const m = s + Math.floor((e - s) / 2);
    this.build(node * 2 + 1, s, m, nums);
    this.build(node * 2 + 2, m + 1, e, nums);
    this.segmentTree[node] = this.segmentTree[node * 2 + 1] + this.segmentTree[node * 2 + 2];
}
/* 
    单点修改change函数
    我们直接修改叶子节点为val,并自下而上递归更新父节点的值
*/
NumArray.prototype.change = function (index, val, node, s, e) {
    if (s === e) {
        this.segmentTree[node] = val;
        return;
    }
    const m = s + Math.floor((e - s) / 2);
    if (index <= m) {
        this.change(index, val, node * 2 + 1, s, m);
    } else {
        this.change(index, val, node * 2 + 2, m + 1, e);
    }
    this.segmentTree[node] = this.segmentTree[node * 2 + 1] + this.segmentTree[node * 2 + 2];
}
/* 范围求和函数 */
NumArray.prototype.range = function (left, right, node, s, e) {
    /* 当 node 对应位区间与[left,right] 相同 可以直接返回该节点的值 */
    if (left === s && right === e) {
        return this.segmentTree[node];
    }
    /*  
        如果不同，设左子节点对应的断点位m ，那么将 [left,right] 沿点 m 
        拆开分别计算出左子节和右子节点
    */
    const m = s + Math.floor((e - s) / 2);
    if (right <= m) {
        return this.range(left, right, node * 2 + 1, s, m);
    } else if (left > m) {
        return this.range(left, right, node * 2 + 2, m + 1, e);
    } else {
        return this.range(left, m, node * 2 + 1, s, m) + this.range(m + 1, right, node * 2 + 2, m + 1, e);
    }
}

var obj = new NumArray([1, 3, 5])
// obj.sumRange(0, 2)
// obj.update(1, 2)
// obj.sumRange(0, 2)
console.log(obj.segmentTree);
/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * obj.update(index,val)
 * var param_2 = obj.sumRange(left,right)
 */